// 时间复杂度: 平均O(nlog2n) 最坏O(nlog2n) 最好O(nlog2n)
// 空间复杂度: O(1)
// 稳定性: 不稳定排序

class HeapSort {
private:
    static void adjustHeap(int *array, int i, int length) {
        while (i * 2 + 1 < length) {
            int k = i * 2 + 1;
            if (k + 1 < length && array[k] < array[k + 1]) {
                k++;
            }

            if (array[i] < array[k]) {
                int temp = array[i];
                array[i] = array[k];
                array[k] = temp;

                i = k;

            } else {
                break;
            }
        }
    }

public:
    static void headSort(int *array, int length) {
        for (int i = length / 2 - 1; i >= 0; --i) {
            adjustHeap(array, i, length);
        }

        for (int i = length - 1; i >= 0; --i) {
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;

            adjustHeap(array, 0, i);
        }
    }
};